﻿// car_monotonic_stack.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        // [[1,2],[2,1],[4,3],[7,2]]
        stack<int>car_st;
        int size = cars.size();
        vector<double>result(size);
        car_st.push(size - 1);
        result[size - 1] = -1;

        for (int i = size - 2; i >= 0; i--)
        {
            double curr_d = cars[i][0];
            double curr_speed = cars[i][1];
            
            while (!car_st.empty())
            {
                int top_i = car_st.top();
                double top_d = cars[top_i][0];
                double top_speed = cars[top_i][1];

                if (top_speed >= curr_speed)
                {
                    car_st.pop();
                }
                else
                {
                    double disappear_time = result[top_i];
                    if (-1 == disappear_time) break;
                    double need_time = (top_d - curr_d) / (curr_speed - top_speed);
                    if (need_time < disappear_time) break;
                    else car_st.pop();
                }
                
            }

            if (car_st.empty())
            {
                result[i] = -1;
            }
            else {
                int top_i = car_st.top();
                double top_d = cars[top_i][0];
                double top_speed = cars[top_i][1];
                double time = (top_d - curr_d) / (curr_speed - top_speed);
                result[i] = time;
            }

            car_st.push(i);
        }
        
        return result;
    }
};

int main()
{
    Solution solu;
    //[[3,4],[5,4],[6,3],[9,1]]
    vector<vector<int>> cars = { {3,4} ,{5,4},{6,3},{9,1} };
    vector<double>result = solu.getCollisionTimes(cars);
    for (auto& item : result)
    {
        cout << item << ' ';
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
